/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(vector<int> &ans, TreeNode *root, int depth)
    {
        if(!root) return;
        if(ans.size() == depth)
            ans.push_back(root->val);

        dfs(ans, root->right, depth + 1);
        dfs(ans, root->left, depth + 1);
        
    }


    vector<int> rightSideView(TreeNode* root) {


        // 除此之外，还有一种递归做法，先遍历右子树，再遍历左子树
        // 有两个问题，怎么记录答案? 怎么知道这个节点该不该记录进去?
        // 就是将节点的深度传给下一层，如果答案的个数和深度一样，则记录
        vector<int> ans;    // 此时答案为空，则答案个数为0，因为ans中没有数据
        dfs(ans, root, 0);       // 这里就是传入深度
        return ans;





        // if(!root) return {};
        // queue<TreeNode*> q;
        // vector<int> ans;
        // q.push(root);
        // while(!q.empty())
        // {
        //     int n = q.size();
        //     TreeNode *tmp = nullptr;    // 用来记录队尾
        //     // int flag = 1;
        //     for(int i = 0; i < n; i++)
        //     {
        //         // if(q.front() != nullptr && flag == 1)
        //         // {
        //         //     ans.push_back(q.front()->val);
        //         //     flag = 0;
        //         // }
        //         // if(q.front())
        //         // {
        //         //     // 注意这里的顺序是先右再左，因为我把空节点也入队列了，所以上面要找到右边第一个不是空节点的数才是暴露在最右边的
        //         //     q.push(q.front()->right);
        //         //     q.push(q.front()->left);
        //         // }
        //         // q.pop();


        //         // 下面我们换一种写法，如果是空节点，那我们就不把它入队列
        //         tmp = q.front();
        //         // 这里顺序就还是先左后右，因为空节点不入队列，从左往右最后一个节点就是暴露在最外面的
        //         if(tmp->left) q.push(tmp->left);
        //         if(tmp->right) q.push(tmp->right);
        //         q.pop();
        //     }
        //     // 因为节点为空时，我们不入队列，所以最后一个就是最左侧节点
        //     ans.push_back(tmp->val);
        // }
        // return ans;
    }
};